package 回文子串专题;

/**
 * @Date 2024/9/7 16:47
 * @description: 回文子串的个数
 * .    https://leetcode.cn/problems/palindromic-substrings/
 * @Author LittleNight
 */
public class likou647 {

    // 练习: 动态规划 时空: O(N^2)
    public int countSubstrings(String s) {
        // 状态表示, dp 表, 初始化, 填表顺序, 返回值
        // 1. dp表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = s.length(), ret = 0;
        boolean[][] dp = new boolean[n][n]; // dp[i][j]表示从i到j这个子串是否是回文串
        // 无需初始化
        // 填表顺序: 从下往上, 左右没有要求
        for (int i = n - 1; i >= 0; i--) {
            // for (int j = 0; j < n; j++) {
            // todo j是从 i 开始的. 不然就会越界
            for (int j = i; j < n; j++) {
                // 不相等的话默认就是false
                if(s.charAt(i) == s.charAt(j)) {
                    if(i == j) dp[i][j] = true; // 就是一个字符
                    else if(i + 1 == j) dp[i][j] = true; // 紧挨着
                    else dp[i][j] = dp[i + 1][j - 1];
                }
                if(dp[i][j]) ret++;
            }
        }
        return ret;
    }

}
